# coding: utf-8

from typing import Optional, Sequence
from stl4py import nth_element
from vec2 import vec2
from graph import Hierarchy, vertex_t, vertex_map, edge_set, NodeAttr, GraphAttr
from .Positioning import Positioning
from .BoundingBox import BoundingBox


class Orient:
    upper_left = 0
    lower_left = 1
    upper_right = 2
    lower_right = 3


class FastAndSimplePositioning(Positioning):

    nodes: vertex_map[NodeAttr]
    boxes: vertex_map[BoundingBox]

    def __init__(
        self,
        attr: GraphAttr,
        nodes: vertex_map[NodeAttr] = None,
        boxes: vertex_map = None,
    ):
        self.attr = attr
        self.nodes = nodes
        self.boxes = boxes
        # TODO

    def init(self, h: Hierarchy):
        # TODO 初始值如何定的呢
        g = h.graph()
        self.conflicting = edge_set(g, "conflicting", lambda: [])
        self.medians = vertex_map(g, "medians", lambda: [-1, -1, -1, -1])
        self.root = vertex_map(g, "root", lambda: [-1, -1, -1, -1])
        self.align = vertex_map(g, "align", lambda: [-1, -1, -1, -1])
        self.sink = vertex_map(g, "sink", lambda: [-1, -1, -1, -1])
        self.shift = vertex_map(g, "shift", lambda: [0.0, 0.0, 0.0, 0.0])
        self.x_ = vertex_map[Optional[float]](g, "x_", lambda: [None, None, None, None])
        # self.boxes = vertex_map(g, 'boxes', lambda: BoundingBox())
        self.max = [-1000000.0, -1000000.0, -1000000.0, -1000000.0]
        self.min = [1000000.0, 1000000.0, 1000000.0, 1000000.0]
        for u in g.get_all_nodes():
            for j in range(4):
                self.root[u][j] = u
                self.align[u][j] = u
                self.sink[u][j] = u
                self.shift[u][j] = 0.0

    def run(self, h: Hierarchy, origin: vec2) -> vec2:
        self.init(h)

        self.init_medians(h)
        # print(self.medians)
        self.mark_conflicts(h)
        # print('---------------------', self.nodes)
        for i in range(4):
            self.vertical_align(h, i)  # i 对应枚举中的值
            self.horizontal_compaction(h, i)
        # print('---------------------', self.nodes)
        min_width_layout = 0  # 相当于 min_width_layout = Orient.upper_left
        for i in range(4):
            if (
                self.max[min_width_layout] - self.min[min_width_layout]
                > self.max[i] - self.min[i]
            ):
                min_width_layout = i

        shift = [0.0, 0.0, 0.0, 0.0]
        for i in range(4):
            if self.left(i):
                shift[i] = self.min[min_width_layout] - self.min[i]
                # self.shift[i] = min[min_width_layout] - min[i]
            else:
                shift[i] = self.min[min_width_layout] - self.max[i]
                # self.shift[i] = min[min_width_layout] - max[i]

        y: float = origin.y
        vals: Sequence[float] = []
        for l in range(h.size()):
            y += self.attr.node_size
            # print(h.layers[l])
            for u in h.layers[l]:
                # if produce_layout < 4:
                #     self.nodes[u].pos = vec2(g.get_node_attr(u,'x_')[produce_layout] + g.get_node_attr(), y)
                #     # self.nodes[u].pos = vec2(x_[produce_layout][u] + self.shift[produce_layout], y)
                # else:
                # TODO
                vals = [
                    self.x_[u][0] + shift[0],
                    self.x_[u][1] + shift[1],
                    self.x_[u][2] + shift[2],
                    self.x_[u][3] + shift[3],
                ]
                vals.sort()
                # vals[1] = 5
                # print(vals[1])

                self.nodes[u].pos = vec2((vals[1] + vals[2]) / 2, y)

                # print(f'每个节点的位置{u}',self.nodes[u].pos)
            y += self.attr.node_size + self.attr.layer_dist
        height = y - self.attr.layer_dist
        width = self.normalize(h, origin.x)

        cross_edge = self.cross_edge_earn(h)
        # for i in range(len(h.layers)-1):
        #     upper = h.layers[i]
        #     # lower = h.layers[layer]
        #     for i in range(len(upper) - 1):
        #         for u in h.g.out_neighbours(upper[i]):
        #             j = h.get_pos(u)
        #             for s in range(i + 1, len(upper)):
        #                 for v in h.g.out_neighbours(upper[s]):
        #                     t = h.get_pos(v)
        #                     if (s > i and t < j) or (s < i and t > j):
        #                         cross_edge.append(upper[i])
        #                         cross_edge.append(u)
        #                         cross_edge.append(upper[s])
        #                         cross_edge.append(v)
        # print('=====================',
        #       upper[i], u, upper[s], v)
        # print(h.g.out_neighbours(55))
        # print(cross_edge)
        # print(cross_edge[::2])  # 奇数位
        # cross_edge[1::2]  # 偶数位
        # 里面的数字不能超过真实的节点的个数，超过的在奇数位的找它的上一个入节点，直到这个节点是真实的节点
        # 在偶数位的找它的下一个出节点，直到这个这个节点是真实的，并将找到的真实节点替换掉虚拟节点

        # 每四个数据为一组看他们的奇数位是否为源点，如果都为源点，任选前两个或后两个数据组成的边删掉，
        #  如果一个为源点另一个不是，就把为源点的及它相邻的偶数位数据组成的边删掉
        # 若两个都不是源点那任选前两个或后两个数据组成的边删掉 或者是 其组成的边暂且不动

        # print(self.nodes[1].pos)
        # print(vec2(width, y - self.attr.layer_dist))            ####坐标点的总宽度
        # for i in g.get_all_nodes():
        # print(self.nodes[0].pos)
        # print(self.nodes[1].pos)
        # print(self.nodes[2].pos)
        # print(self.nodes[3].pos)

        return vec2(width, y - self.attr.layer_dist), cross_edge

    def cross_edge_earn(self, h: Hierarchy):
        cross_edge = []
        for i in range(len(h.layers) - 1):
            upper = h.layers[i]
            # lower = h.layers[layer]
            for i in range(len(upper) - 1):
                for u in h.g.out_neighbours(upper[i]):
                    j = h.get_pos(u)
                    for s in range(i + 1, len(upper)):
                        for v in h.g.out_neighbours(upper[s]):
                            t = h.get_pos(v)
                            if (s > i and t < j) or (s < i and t > j):
                                cross_edge.append(upper[i])
                                cross_edge.append(u)
                                cross_edge.append(upper[s])
                                cross_edge.append(v)
                                # print('=========================',
                                #       upper[i], u, upper[s], v)
        # print("存在虚拟节点时的交叉边", cross_edge)
        # ---------------------------------------------------------
        # DOTO
        real_nodes = list(range(187))  # 真实节点的范围是0到99
        # real_nodes = list(range(28))
        for i in range(len(cross_edge)):

            if cross_edge[i] not in real_nodes:  # 如果节点是虚拟的

                if i % 2 == 0:  # 如果节点在奇数位
                    j = h.g.in_neighbours(cross_edge[i])

                    while j[0] not in real_nodes:
                        j = h.g.in_neighbours(j[0])
                    cross_edge[i] = j[0]  # 找到上一个真实节点并替换掉虚拟节点
                else:  # 如果节点在偶数位
                    j = h.g.out_neighbours(cross_edge[i])
                    while j[0] not in real_nodes:
                        j = h.g.out_neighbours(j[0])
                    cross_edge[i] = j[0]  # 找到下一个真实节点并替换掉虚拟节点

        return cross_edge

    def horizontal_compaction(self, h: Hierarchy, dir: int):
        g = h.graph()
        # TODO
        # sink = self.sink[dir]
        # root = self.root[dir]
        # shift = self.shift[dir]
        # x_ = self.x_[dir]
        # TODO
        for u in g.get_all_nodes():
            # print(u, self.root[u])
            if self.root[u][dir] == u:
                self.place_block(h, u, dir)
        for i in self.idx_range(h.size(), self.up(dir)):
            layer = h.layers[i]
            for u in layer:
                self.x_[u][dir] = (
                    self.x_[self.root[u][dir]][dir]
                    + self.shift[self.sink[self.root[u][dir]][dir]][dir]
                )

                if self.x_[u][dir] > self.max[dir]:
                    self.max[dir] = self.x_[u][dir]
                if self.x_[u][dir] < self.min[dir]:
                    self.min[dir] = self.x_[u][dir]

    def normalize(self, h: Hierarchy, start: float) -> float:
        minimum = 1000000
        maximum = -1000000
        g = h.graph()
        for u in g.get_all_nodes():
            if (
                self.nodes[u].pos.x + self.boxes[u].size.x - self.boxes[u].center.x
                > maximum
            ):
                maximum = (
                    self.nodes[u].pos.x + self.boxes[u].size.x - self.boxes[u].center.x
                )

            if self.nodes[u].pos.x - self.boxes[u].center.x < minimum:
                minimum = self.nodes[u].pos.x - self.boxes[u].center.x

        for u in g.get_all_nodes():
            self.nodes[u].pos.x = start + self.nodes[u].pos.x - minimum

        return maximum - minimum

    def init_medians(self, h: Hierarchy):
        g = h.graph()
        neighbours: Sequence[int] = []
        for u in g.get_all_nodes():
            # TODO
            neighbours.extend(g.out_neighbours(u))

            left, right = self.median(h, u, neighbours)

            self.medians[u][Orient.lower_left] = left
            self.medians[u][Orient.lower_right] = right

            neighbours.clear()

            neighbours.extend(g.in_neighbours(u))
            left, right = self.median(h, u, neighbours)
            self.medians[u][Orient.upper_left] = left
            self.medians[u][Orient.upper_right] = right
            neighbours.clear()

    # -> Tuple[vertex_t, vertex_t]:
    def median(self, h: Hierarchy, u: vertex_t, neigh: Sequence[vertex_t]):
        count: int = len(neigh)
        # print(count)  # 长度从一开始，但标签从零开始
        # TODO
        # m: int = math.floor(count / 2)  # 向下取整
        m = count // 2
        if count == 0:
            return u, u
        nth_element(neigh, m, first=0, last=count, key=lambda v: h.get_pos(v))
        right = neigh[m]
        if count % 2 == 1:
            return right, right
        nth_element(neigh, m - 1, first=0, last=count, key=lambda v: h.get_pos(v))

        return neigh[m - 1], right

    def is_inner(self, h: Hierarchy, u: vertex_t) -> bool:
        g = h.graph()
        if g.out_degree(u) != 1 or not g.is_dummy_node(u):
            return False
        out_neighbours = g.out_neighbours(u)
        if out_neighbours:
            first_out_neighbour = out_neighbours[0]
            return g.is_dummy_node(first_out_neighbour)
        return False

    def inner_pos(self, h: Hierarchy, u: vertex_t) -> int:
        g = h.graph()

        out_neighbours = g.out_neighbours(u)
        if out_neighbours:
            first_out_neighbour = out_neighbours[0]
        return h.get_pos(first_out_neighbour)

    def mark_conflicts(self, h: Hierarchy):
        g = h.graph()
        if h.size() < 4:
            return
        for i in range(1, h.size() - 2):
            last_pos: int = 0
            p: int = 0
            for j in range(len(h.layers[i])):
                lay = h.layers[i]
                u = lay[j]
                if j == len(h.layers[i]) - 1 or self.is_inner(h, u):
                    curr_pos = len(h.layers[i + 1])
                    if self.is_inner(h, u):
                        curr_pos = self.inner_pos(h, u)
                    while p <= j:
                        pth = h.layers[i][p]
                        for v in g.out_neighbours(pth):
                            if h.get_pos(v) < last_pos or h.get_pos(v) > curr_pos:
                                self.conflicting.insert(pth, v)
                        p += 1
                    last_pos = curr_pos

    def vertical_align(self, h: Hierarchy, dir: int):  # 直接传枚举的值
        # TODO align = this->align[dir]
        g = h.graph()

        # align = g.get_node_attr()[dir]
        # align = self.align[dir]
        # root = self.root[dir]

        for l in self.idx_range(h.size(), not self.up(dir)):
            layer = h.layers[l]
            m_pos: int = 0 if self.left(dir) else g.node_count()
            d: int = 1 if self.left(dir) else -1

            for k in self.idx_range(len(layer), not self.left(dir)):
                u: vertex_t = layer[k]

                # for m in [g.get_node_array_attr(u,"medians", dir), self.medians[self.invert_horizontal(dir)][u]]:
                for m in [
                    self.medians[u][dir],
                    self.medians[u][self.invert_horizontal(dir)],
                ]:

                    if (
                        m != u
                        and self.align[u][dir] == u
                        and not self.is_conflicting(u, m, dir)
                        and d * h.get_pos(m) >= d * m_pos
                    ):
                        self.align[m][dir] = u
                        self.root[u][dir] = self.root[m][dir]
                        self.align[u][dir] = self.root[m][dir]

                        m_pos = h.get_pos(m) + d

    def place_block(self, h: Hierarchy, u: vertex_t, type: int):
        if self.x_[u][type] is not None:
            return

        self.x_[u][type] = 0
        d = 1
        if self.left(type):
            d = -1
        w: vertex_t = u
        # TODO
        while True:
            if not self.is_last_idx(
                h.get_pos(w), len(h.get_layer(w)), not self.left(type)
            ):
                v: vertex_t = h.get_layer(w)[h.get_pos(w) + d]
                rv: vertex_t = self.root[v][type]
                # TODO
                self.place_block(h, rv, type)
                if self.sink[u][type] == u:
                    self.sink[u][type] = self.sink[rv][type]
                if self.sink[u][type] != self.sink[rv][type]:
                    new_shift: float = (
                        self.shift[self.sink[rv][type]][type]
                        + self.x_[rv][type]
                        - self.x_[u][type]
                        - d
                        * (
                            self.node_dist(v, w)
                            if self.left(type)
                            else self.node_dist(w, v)
                        )
                    )
                    # new_shift: float = shift[sink[rv]] + x[rv] - x[u] - d * (self.node_dist(v, w) if self.left(type) else self.node_dist(w, v))
                    self.shift[self.sink[u][type]][type] = (
                        max(self.shift[self.sink[u][type]][type], new_shift)
                        if not self.left(type)
                        else min(self.shift[self.sink[u][type]][type], new_shift)
                    )
                else:
                    new_x: float = self.x_[rv][type] - d * (
                        self.node_dist(v, w)
                        if self.left(type)
                        else self.node_dist(w, v)
                    )
                    self.x_[u][type] = (
                        min(self.x_[u][type], new_x)
                        if not self.left(type)
                        else max(self.x_[u][type], new_x)
                    )

            w = self.align[w][type]
            # print(w)
            if w == u:
                break

    def left(self, dir: int) -> bool:
        return dir == Orient.upper_left or dir == Orient.lower_left

    def up(self, dir: int) -> bool:
        return dir == Orient.upper_left or dir == Orient.upper_right

    def is_conflicting(self, u: vertex_t, med: vertex_t, dir: int) -> bool:
        return (self.up(dir) and self.conflicting.contains(med, u)) or (
            not self.up(dir) and self.conflicting.contains(u, med)
        )

    def node_dist(self, u: vertex_t, v: vertex_t) -> float:
        return (
            self.boxes[u].size.x
            - self.boxes[u].center.x
            + self.boxes[v].center.x
            + self.attr.node_dist
        )
        # return self.boxes[u].size.x - self.boxes[u].center.x + self.boxes[v].center.x + self.attr.node_dist

    def idx_range(self, size: int, desc: bool) -> range:
        if desc:
            return range(size - 1, -1, -1)
        else:
            return range(0, size, 1)

    # Is i one of the endpoints of the interval <0, size - 1>
    def is_last_idx(self, i: int, size: int, desc: bool) -> bool:
        if desc:
            return i == size - 1
        else:
            return i == 0

    def invert_horizontal(self, dir: int) -> int:
        if dir == Orient.upper_left:
            return Orient.upper_right
        elif dir == Orient.upper_right:
            return Orient.upper_left
        elif dir == Orient.lower_left:
            return Orient.lower_right
        elif dir == Orient.lower_right:
            return Orient.lower_left
        else:
            assert False
            return Orient.upper_left
